class Solution {
public:
    int numWays(int n, vector<vector<int>>& relation, int k) {
        int m = relation.size();
        vector<vector<int>> dp(k+1,vector<int>(n));
        dp[0][0] = 1;
        
        for(int step = 1;step <= k;step++){
            for(auto& vc : relation){
                if(dp[step-1][vc[0]] != 0){
                    dp[step][vc[1]] += dp[step-1][vc[0]];
                }
            }
        }
        return dp[k][n-1];
    }
};
